package twoD;

/**
 * @author pengfei.hpf
 * @date 2020/4/3
 * @verdion 1.0.0
 *
 * 1139. 最大的以 1 为边界的正方形
 * 给你一个由若干 0 和 1 组成的二维网格 grid，请你找出边界全部由 1 组成的最大 正方形 子网格，并返回该子网格中的元素数量。如果不存在，则返回 0。
 *
 *
 *
 * 示例 1：
 *
 * 输入：grid = [[1,1,1],[1,0,1],[1,1,1]]
 * 输出：9
 * 示例 2：
 *
 * 输入：grid = [[1,1,0,0]]
 * 输出：1
 *
 *
 * 提示：
 *
 * 1 <= grid.length <= 100
 * 1 <= grid[0].length <= 100
 * grid[i][j] 为 0 或 1
 */
public class Largest1BorderedSquare {
    public int largest1BorderedSquare(int[][] grid) {
        if(grid == null || grid.length == 0 || grid[0].length == 0){
            return 0;
        }
        int max = 0;
        for(int i = 0; i < grid.length; i ++){
            for(int j = 0; j < grid[0].length; j++){
                if(grid[i][j] == 1){
                    int len = getMax(grid, i, j);
                    if(len > max){
                        max = len;
                    }
                }
            }
        }
        return max*max;
    }

    private int getMax(int[][] grid, int row, int col){
        int m = grid.length;
        int n = grid[0].length;
        int min = 1;
        for(int i  = row + 1; i < m; i ++){
            if(grid[i][col] == 1){
                min ++;
            } else {
                break;
            }
        }
        int count = 1;
        for(int i = col + 1; i < n; i ++){
            if(grid[row][i] == 1){
                count ++;
            } else {
                break;
            }
        }
        min = Math.min(min, count);
        count = min;
        while(count > 1){
            int c = col + count - 1;
            int r = row + count - 1;
            boolean isMatch = true;
            for(int i = row + 1; i <= r; i ++){
                if(grid[i][c] == 0){
                    isMatch = false;
                }
            }
            for(int i = col + 1; i <= c; i++){
                if(grid[r][i] == 0){
                    isMatch = false;
                }
            }
            if(isMatch){
                break;
            }
            count --;
        }
        return count;
    }
}
